package leetcode.滑动窗口;

import java.util.HashSet;
import java.util.Set;

/**
 *
 * 无重复字符的最长子串
 *
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 示例 1:
 *
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 */
public class Test3无重复字符的最长子串 {

    // 滑动窗口法
    public static int lengthOfLongestSubstring2(String s) {
        int l = 0;
        int r = -1;
        int maxLength = 0;
        int[] ascii = new int[256]; // 利用ASCII码去重而非 set 的 api
        while (l < s.length()) {
            // ASCII 里面默认都是0，如果遍历s到ASCII中的某一个位置时发现为 0 表示没有遇到过
            // 所以窗口要扩大
            // 防止越界
            if (r+1 < s.length() && ascii[s.charAt(r + 1)] == 0) {
                ascii[s.charAt(++r)] = 1;
            } else {
                ascii[s.charAt(l++)] = 0;
            }

            maxLength = Math.max(maxLength, r - l + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring2(s));
    }






    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 1)
            return 1;
        if (s.length() == 0)
            return 0;
        char str[] = s.toCharArray();
        int i = 0, j = i + 1, max = 0;
        boolean flag = true;
        while (i < s.length() - 1) {
            int length = 1;
            //检测是否重复
            if (j == s.length())
                break;
            for (int k = i; k < j; k++) {
                if (str[j] != str[k]) {
                    length++;
                } else {
                    flag = false;
                    break;
                }
            }
            if (length > max) {
                max = length;
            }
            //如果不重复，j指针右移一次
            if (flag)
                j++;
            //重复，i指针右移一次，j指针回到i+1的位置
            else {
                flag = true;
                i++;
                j = i + 1;
                length = 1;
            }
        }
        return max;
    }

    public static boolean isUnique(String str, int s, int e) {
        // Java提供了集合Set，它的特点是值必须唯一，不能出现重复的
        Set<Character> set = new HashSet<>();
        // 用循环查找set里面是否存在str里面出现过的字符
        for (int k = s; k < e; k++) {
            // 取str的每一个单个的字符
            Character c = str.charAt(k);
            if (set.contains(c)) {
                return false;
            }
            // 既然不存在就存放到set里面，用来和str的下一个字符比较
            set.add(c);
        }
        // 没有找到相同的字符就返回true
        return true;
    }


}